package backtrack;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

public class Solution_17 {

    List<String> res = new ArrayList<>();

    /**
     * 注意这里可以写digits.equals("")，但不能用==，==能不用就不用
     */
    public List<String> letterCombinations(String digits) {
        Map<Character, String> map = Map.of('2', "abc",
                '3', "def",
                '4', "ghi",
                '5', "jkl",
                '6', "mno",
                '7', "pqrs",
                '8', "tuv",
                '9', "wxyz");
        StringBuilder sb = new StringBuilder();
        dfs(0, digits, map, sb);
        return res;
    }

    private void dfs(int i, String digits, Map<Character, String> map, StringBuilder sb) {
        if (i == digits.length()) {
            res.add(new String(sb));
            return;
        }
        String cur = map.get(digits.charAt(i));
        for (int j = 0; j < cur.length(); j++) {
            sb.append(cur.charAt(j));
            dfs(i + 1, digits, map, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        Solution_17 solution17 = new Solution_17();
        System.out.println(solution17.letterCombinations("2"));
    }
}
